package leetcode_core.leetcode_1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class MaxSlidingWindow {
    class MonotonicQueue{
        private LinkedList<Integer> q = new LinkedList<>();
        public void push(int n){//在队尾添加元素n
            while(!q.isEmpty() && q.getLast()<n){
                q.pollLast();
            }
            q.addLast(n);
        }
        int max(){
            return q.getFirst();
        }
        void pop(int n){//队头元素如果是n,那么删除它
            if(n == q.getFirst()){
                q.pollFirst();
            }
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        MonotonicQueue window = new MonotonicQueue();
        for(int i = 0;i<nums.length;i++){
            //先把窗口的k-1给填满
            if(i<k-1){
                window.push(nums[i]);
            }else{//开始滑动窗口
                //窗口向前滑动
                //移入新元素
                window.push(nums[i]);
                //将当前窗口中的最大元素计入结果
                list.add(window.max());
                //移出最后到的元素
                window.pop(nums[i-(k-1)]);
            }
        }
        int[] arr = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            arr[i] = list.get(i);
        }
        return arr;
    }
}
